package com.hashmap;

import java.util.Objects;

/**
 * @author XiaoPan
 * date: 2022/1/17 16:13
 * <p>
 * action:  实现 hashmap
 */
public class TestMap<K, V> {


    // hashmap 初始 容量 为 16
    private Integer CAPACITY = 16;

    private Node<K, V>[] objects;

    private Integer size = 0;


    //初始化
    public TestMap() {
        this.objects = new Node[CAPACITY];
    }

    public int size() {
        return size;
    }

    // 增加
    public void put(K key, V value) {
        if (size >= objects.length / 4 * 3) {
            if (judge()) {
                capacityExpansion2();
            }
        }

        int i = key.hashCode();
        Node<K, V> newNode = new Node<>(key, value, null);

        int i1 = i % CAPACITY;

        if (objects[i1] == null) {
            size++;
            objects[i1] = newNode;
            return;
        }

        Node<K, V> node = forEac2(objects[i1], key);

        if (node == null) {
//            node.setNext(newNode);
//            没有找到
            if (objects[i1].getNext() != null) {
                //有第一个节点
                //将 新的节点 放到 第一个
                newNode.setNext(objects[i1].getNext());
            }
            objects[i1].setNext(newNode);
//            大小加1
            size++;
        } else {
            node.setValue(value);
        }
    }

    public V get(K key) {
        int i = key.hashCode();
        int i1 = i % CAPACITY;
        if (objects[i1] == null) return null;
        Node<K, V> node = forEac2(objects[i1], key);
        if (node == null) {
            return null;
        }
        return node.getValue();
    }

    /**
     * 如果有的话 就 返回 那个 节点  没有的话 就返回null;
     */
    private Node<K, V> forEac2(Node<K, V> node, K key) {

        Node<K, V> key1 = new Node(key, 0, null);

        while (!(key1.equals(node))) {
            //没有找到
            if (node.getNext() == null) {
                return null;
            }
            node = node.getNext();
        }
        return node;
    }

    public boolean containsKey(K key) {
        for (Node<K, V> object : objects) {
            if (object == null) continue;
            Node<K, V> kvNode = forEac2(object, key);
            if (kvNode != null) return true;
        }
        return false;
    }


    // todo 扩容
//    public void capacityExpansion() {
//        //扩为原来的两倍
//        CAPACITY = CAPACITY * 2;
//        //获得原来两倍的 的大小的 数组
//        Node<K, V>[] newObj = new Node[CAPACITY];
//
//        Node<K, V> key1 = null;
//
//        for (Node<K, V> object : objects) {
//
//            while (object != null) {
//                int i = object.getKey().hashCode() % CAPACITY;
//
//                if (newObj[i] == null) {
//                    newObj[i] = object;
//                    newObj[i].setNext(null);
//                } else {
//                    if (newObj[i].getNext() != null) {
//                        key1 = newObj[i].getNext();
//                    } else {
//                        newObj[i].setNext(object);
//                        newObj[i].getNext().setNext(null);
//                    }
//
//                    while (key1 != null) {
//                        key1 = key1.getNext();
//                    }
//                    key1 = object;
//                }
//
//                if (object.getNext() == null) {
//                    break;
//                }
//                object = object.getNext();
//            }
//        }
//        objects = newObj;
//    }


    private void capacityExpansion2() {
        size = 0;
        //扩为原来的两倍
        CAPACITY = CAPACITY * 2;
        //获得原来两倍的 的大小的 数组
        Node<K, V>[] newObj = new Node[CAPACITY];

        Node<K, V>[] Obj2 = objects;

        objects = newObj;

        for (Node<K, V> kvNode : Obj2) {
            if (kvNode != null) {
                K key = kvNode.getKey();
                V value = kvNode.getValue();
                put(key, value);

                while (kvNode.getNext() != null) {
                    kvNode = kvNode.getNext();
                    K key1 = kvNode.getKey();
                    V value1 = kvNode.getValue();
                    put(key1, value1);
                }
            }
        }
    }

    public void capacityExpansion3(){

    }










    public V remove(K key) {

        for (int i = 0; i < objects.length; i++) {
            if (objects[i] == null) continue;
            Node<K, V> kvNode = forEac2(objects[i], key);
            if (kvNode != null) {
                //找到了
                V value = kvNode.getValue();
                //   无法修改
                Node<K, V> next = objects[i];
                if (next.equals(kvNode)) {
                    objects[i] = kvNode.getNext();
                }
                while (true) {
                    if (next.getNext().equals(kvNode)) {
                        next.setNext(kvNode.getNext());
                        break;
                    }
                    next = next.getNext();
                }
                return value;
            }
        }


//        for (Node<K, V> object : objects) {
//            if (object == null) continue;
//            Node<K, V> kvNode = forEac2(object, key);
//            if (kvNode != null) {
//                //找到了
//                V value = kvNode.getValue();
//                if (kvNode.getNext() == null) {
//                    kvNode = null;
//                } else {
//                    //   无法修改
//                    Node<K, V> next = object;
//                    if (next.equals(kvNode)) {
//                        object = kvNode.getNext();
//                    }
//                    while (next.getNext().equals(kvNode)) {
//                        next = kvNode.getNext();
//                    }
//                }
//                return value;
//            }
//        }
        //没有找到
        return null;
    }


    //判断是否需要扩容
    private boolean judge() {
        int o = 0;
        for (Node<K, V> object : objects) {
            if (object != null) {
                o++;
            }
        }

//        需要扩容
        if (objects.length / 4 * 3 <= o) {
            return true;
        }
        return false;
    }


}

class Node<T, E> {
    T key;
    E value;
    Node<T, E> next;

    public Node(T key, E value, Node<T, E> next) {
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public T getKey() {
        return key;
    }

    public void setKey(T key) {
        this.key = key;
    }

    public E getValue() {
        return value;
    }

    public void setValue(E value) {
        this.value = value;
    }

    public Node<T, E> getNext() {
        return next;
    }

    public void setNext(Node<T, E> next) {
        this.next = next;
    }


    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Node<?, ?> node = (Node<?, ?>) o;
        return Objects.equals(key, node.key);
    }
}
